package week_four;

public class FindFirstAndLastPositionInSortedArray_34 {
    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length;
        int lBound = -1, rBound = -1;
        //找左边界, lower_bound，第一个>=target的数
        //范围 [0, n]
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target)
                r = mid;
            else
                l = mid + 1;
            lBound = r;
        }

        l = -1;
        r = nums.length - 1;
        //找右边界，最后一个<=target的数
        //范围[-1, n-1], 计算mid时，left+1
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
            rBound = r;
        }

        if (rBound < lBound) return new int[]{-1, -1};
        else return new int[]{lBound, rBound};
    }
}
